# 使用numpy模块生成随机数
import numpy as np
# 二分查找库函数
import bisect

import time

def calcTime(func):
    '''
    函数修饰器, 用来计算算法的执行时间
    最终返回一个 list [temp, time_sum]
                    temp : 运行结果
                    time_sum : 算法执行时间(单位ms)
    '''
    def warpper(arr1,arr2):
        time_start = time.perf_counter()
        temp = func(arr1,arr2)
        time_end = time.perf_counter()
        time_sum = time_end - time_start
        return [temp, time_sum *1000]
    return warpper

# 随机生成[1,7)的长度为n的分数数组arrs
def arrs(n):
    arr1 = list(np.random.randint(1, 7, size=n))
    arr2 = list(np.random.randint(1, 7, size=n-2))
    return [arr1,arr2]

@calcTime
def makeArrayIncreasing(arr1, arr2):
        # 预处理：排序，去重，加哨兵
        maxv = 999999
        arr1 = [-1] + arr1 + [maxv + 5]
        arr2 = sorted(list(set(arr2)))
        n = len(arr1)

        dp = [0] + [maxv]*(n-1)
        for i in range(1,n):
            j = bisect.bisect_left(arr2, arr1[i])
            for k in range(1, min(i-1, j) + 1):  # 枚举替换的个数 k = 1 to min(i-1,j)
                if arr1[i-k-1] < arr2[j-k]:
                    dp[i] = min(dp[i], dp[i-k-1] + k)
            if arr1[i-1] < arr1[i]:              # 不替换 arr1[i-1]
                dp[i] = min(dp[i], dp[i-1])
        return dp[-1] if dp[-1] < maxv else -1

#算法测试
if __name__ == '__main__':
    for i in range(3):
        result=arrs(5)
        arr1=result[0]
        arr2=result[1]
        print(arr1)
        print(arr2)
        print(makeArrayIncreasing(arr1,arr2))

"""
测试结果：
[5, 2, 4, 4, 4]
[3, 1, 5]
[3, 0.036200000000041754]
[4, 1, 5, 6, 5]
[1, 5, 6]
[-1, 0.02179999999996074]
[2, 5, 5, 6, 1]
[3, 3, 6]
[-1, 0.01979999999990323]
"""